next와 prev로 이동하기
출발 노드와 이동 방향을 바꾸면 current가 따라가는 참조가 달라진다. prev가 없으면 현재 노드에서 바로 뒤로 갈 수 없다.
현재 상태
노드당 참조
역방향 이동
prev 하나를 더 저장하면 현재 노드에서 앞선 노드로 직접 이동할 수 있다. 단일 연결리스트에서는 앞 노드를 따로 기억하거나 head에서 다시 찾아야 한다.
노드 참조를 알고 있을 때 연결 바꾸기
B와 C 사이에 X를 삽입하거나 C를 삭제한다. 단계를 옮기면 바뀐 필드와 아직 보존된 기존 참조를 함께 볼 수 있다.
현재 상태
노드 위치 찾기비용에서 제외
참조 변경Θ(1)
인덱스로 요청하면 먼저 노드를 찾아야 한다. 노드 참조가 이미 주어졌다면 삽입은 참조 네 개, 삭제는 참조 두 개만 바꾸므로 입력 크기와 관계없이 Θ(1)이다.